package com.yaoli.ajob;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 递归方法
 *
 * 通常 有很多情况的 题目 可以使用 递归方法，即回溯 方法
 *
 * Created by will on 2017/4/16.
 */
public class _093_RestoreIPAddresses {
    public static void main(String[] args) {
        _093_RestoreIPAddresses restoreIPAddresses = new _093_RestoreIPAddresses();

        //["0.10.0.10","0.100.1.0"]

        //["0.1.0.010","0.1.00.10","0.1.001.0","0.10.0.10","0.10.01.0",
        // "0.100.1.0","01.0.0.10","01.0.01.0","01.00.1.0","010.0.1.0"]
        restoreIPAddresses.restoreIpAddresses("010010");
    }

    List<String> list = new ArrayList<String>();

    public List<String> restoreIpAddresses(String s) {

        if(s.length() > 12 || s.length() < 4){
            return list;
        }else{
            calc("",s,"",0);
        }


        return list;
    }


    public void calc(String num,String remain,String result,int deep){

        if(!num.equals("")){

            //排除 有前导0 的情况
            if( (num.length() > 1 && num.charAt(0) == '0') ||
                    (num.length() > 2 && num.charAt(0) == '0' && num.charAt(1) == '0'))
                return;

            if(Integer.valueOf(num) <= 255){
                if(result.equals("")){
                    result = num;
                }else{
                    result = result + "." + num;
                }
            }else{
                return;
            }
        }

        if(deep == 4 && remain.length() > 0){
            return;
        }

        if(deep == 4){
            list.add(result);
        }

        if(remain.length() >= 1){
            calc(remain.substring(0,1),remain.substring(1),result,deep + 1);
        }

        if(remain.length() >= 2){
            calc(remain.substring(0,2),remain.substring(2),result,deep + 1);
        }

        if(remain.length() >= 3){
            calc(remain.substring(0,3),remain.substring(3),result,deep + 1);
        }
    }
}
